package 中等.贪心思想;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
 * <p>
 * 注意:
 * <p>
 * 可以认为区间的终点总是大于它的起点。
 * 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/non-overlapping-intervals
 */
public class 无重叠区间_435 {

    public static void main(String[] args) {

        int[][] inervals = {{1, 100}, {12, 22}, {1, 11}, {3, 12}, {2, 3}};

        System.out.println(efficientEraseOverlapIntervals(inervals));

    }

    /**
     * 排序+动态规划
     * 求出不存在重叠区间的最多元素
     * 子问题：
     * 加上intervals的某个元素的最多不存在重叠区间的做多元素
     * 分析：
     * 循环到当前元素的最多不重叠区间=max(当前元素的最多不重叠区间,之前每一个元素的最多不重叠区间+当前元素(1))
     * dp[i] = Math.max(dp[i], dp[j] + 1)
     *
     * @param intervals
     * @return
     */
    public static int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];
            }
        });
        int n = intervals.length;
        int[] dp = new int[n];
        //每一个元素都是一个不重叠区间
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (intervals[j][1] <= intervals[i][0]) {
                    //如果当前元素与之前的某个元素不存在重叠区间，那么当前元素的做多不重叠区间=之前某个元素的最多不重叠区间+1
                    //如果当前元素与之前多个元素都不存在重叠区间，那么取最大的
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return n - Arrays.stream(dp).max().getAsInt();
    }

    /**
     * 排序+贪心+模拟
     * 排序+贪心，当循环到某一个元素时，将它之前的每一个元素与之比较，如果存在重叠区间，
     * 则直接删除当前元素，因为是根据区间的右侧进行排序，当前元素右侧是属于最大的，删除当前元素属于最优
     * 模拟删除可以用将右侧元素设置为最小，则下次判断到该区间时，必为不重叠区间
     * <p>
     * 时间复杂度(O(n*n))，空间复杂度，因为需要排序，空间复杂度为(O(n*log(n)))
     *
     * @param intervals
     * @return
     */
    public static int eraseOverlapIntervals2(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];
            }
        });
        int del = 0;
        for (int i = 1; i < intervals.length; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[i][0] < intervals[j][1]) {
                    //去除区间右边比较大的区间
                    intervals[i][1] = Integer.MIN_VALUE;
                    del++;
                    break;
                }
            }
        }
        return del;
    }

    /**
     * 排序+贪心+模拟
     * 不需要每次都从第一位元素与当前元素比较，如果有符合条件的区间，则前面的区间必符合条件
     * 因为是按照右边界进行排序，
     * 如果当前元素cur[0]>前一个元素pre[1]，
     * 且next[0]>cur[1]
     * 又因为 cur[1]>cur[0]
     * 所以 next[0]>pre[1]
     * 所以当前元素cur之前符合条件的pre区间必然也符合条件
     *
     * @param intervals
     * @return
     */
    public static int eraseOverlapIntervals3(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];
            }
        });
        int del = 0;
        int ok = 0;
        for (int i = 1; i < intervals.length; i++) {
            for (int j = ok; j < i; j++) {
                if (intervals[i][0] < intervals[j][1]) {
                    //去除区间右边比较大的区间
                    intervals[i][1] = Integer.MIN_VALUE;
                    del++;
                    break;
                } else {  //如果有符合条件的区间，则左侧的区间都符合条件
                    ok = j;
                }
            }
        }
        return del;
    }

    /**
     * 排序+贪心
     * 单循环
     * 每次判断当前元素与之间ok的元素是否存在重复区间，
     * 如果不存在重复区间，则将ok的元素设置为当前元素，
     * 当然，ok之前的元素也必然符合不存在重复区间的条件
     * 其中的"删除的元素"永远不会被用于与当前元素的判断
     *
     * @param intervals
     * @return
     */
    public static int efficientEraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        //lambda
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int del = 0;
        int ok = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[ok][1]) {
                //当前元素存在重复区间，要删除的区间+1
                //按照区间的右边界进行排序，每次遇到重复区间，贪心的选择左边的ok的区间，因为它始终都是最小的，
                del++;
            } else {  //如果不存在重复区间，那么将当前元素设置为最左边的符合条件的边界元素
                ok = i;
            }
        }
        return del;
    }

}
